![]()
문제알고리즘문제에 "이 마을에 막다른 길이 없다면, 상근이는 임의의 한 길에서 시작해서, 갈 수 있는 어떤 방향으로 움직이더라도, 유턴을 하지 않고 그 위치로 돌아올 수 있어야 한다." 라는 조건이 존재하므로, 어떤 길에서 이동할 수 있는 길이 1이하 칸이 존재한다면 해당 마을에는 막다른 길이 존재하게 된다.그러므로 모든칸을 조사하면서 상,하,좌,우로 움직일 수 있는 칸의 개수를 카운팅하면서 1이하인 칸이 존재한다면 해당 마을은 막다른 길이 된다.코드import sysinput = sys.stdin.readliner, c = map(int, input().split())arr = [input().strip() for _ in range(r)]dx = [-1, 1, 0, 0]dy = [0, 0, 1, -1..
문제 https://www.acmicpc.net/problem/18126텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다. 구구의 집으로 들어가는 입구는 한 개이며 입구과 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는 무더운 여름 햇살을 피해 최대한 입구에서 먼 방에 아이스크림을 숨기려고 한다.구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라. 입력첫째 줄에 정수 N(1 ≤ N ≤ 5,000)이 주어진다.다음 N-1개의 줄에 구구의 집의 모든 길의..
import sysinput = sys.stdin.readlineN, M = map(int, input().split())arr1 = list(map(int, input().split()))arr2 = list(map(int, input().split()))arr = arr1 + arr2arr.sort()print(*arr) https://www.acmicpc.net/problem/11728문제정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.입력첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 ..
![]()
문제 https://www.acmicpc.net/problem/11726 Algorithm2 * n 크기의 직사각형을 채우는 방법은 마지막에 2 * 1 타일을 새로로 두는지 가로로 두는지에 따라 달라집니다.이를 이용해 피보나치 수열과 유사한 점화식을 사용합니다. Coden = int(input())dp = [0] * (n + 2)dp[1] = 1if n >= 2: dp[2] = 2for i in range(3, n + 1): dp[i] = (dp[i - 1] + dp[i - 2]) % 10007print(dp[n])
![]()
문제알고리즘출발한 칸에 따라서 총 몇개의 칸을 밟는지 계산하는 문제이다.내가 i번째 칸에서 시작했다고 했을때, i+k 번째 칸을 밟는다고 가정하면 i번째 칸에서 i+k번째 칸으로 갈때까지 밟는 칸수와 i+k에서시작했을때 밟는 칸수의 합이 답이 되므로 역순으로 계산하면 편리하겠다고 생각했다.예시를 확인하면9에서 시작하면 9만 밟게 되므로 1칸8에서 시작하면 8만 밟게 되므로 1칸, 8 + 3은 N = 9인 경우를 넘어가버리므로 제외한다.7에서 시작하면 7, 8을 밟게 되므로 2칸, 7에서 8로 갈때 1칸을 밟고 8에서 시작한 경우 +1 해서 2칸이다.6에서 시작하면 6,7,8을 밟게 되므로 3칸, 6에서 7로 갈때 1칸을 밟고 7에서 시작한 경우 +2해서 3칸이다.5에서 시작하면 5,7,8을 밟게 되므로 ..
9095번: 1, 2, 3 더하기 숫자들을 5까지 계산해보면 직전 3개까지의 합이라는 걸 알 수 있다.왜냐면 우리가 쓸 수 있는 수는 1,2,3 3가지이고, 이전에 썼던 것에 대해 1차이 나면 뒤에 1을 더해주기, 2차이 나면 2를 더해주기 3차이나면 3을 더해주기...로 해결되기 때문이다. 뒤에더하든 앞에더하든 아무튼 한 쪽 방향으로 쭉 더해줘야 중복이 나오지 않는다 def main(): t = int(input()) arr = [0 for _ in range(11)] # print(arr) arr[1] = 1 arr[2] = 2 arr[3] = 4 def dp(k): if arr[k] == 0: arr[k] = dp(k-1)+dp(..
문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.예제 입력 1 610 20 10 30 20 50예제 출력 1 4증가부분수열에서 특정 원소가 마지막 값이 되려면, 그 원소보다 작은 값들로만 이루어진 수열의 끝에 추가되어야 한다. 따라서 A[i]를 마지막으로 하는 ..
미로 만들기문제홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍준이는 미로에서 모든 행과 열의 이동할 수 있는 칸을 걸어다녔다. 그러면서 자신의 움직임을 모두 노트에 쓰기로 했다. 홍준이는 미로의 지도를 자기 노트만을 이용해서 그리려고 한다.입력으로 홍준이가 적은 내용을 나타내는 문자열이 주어진다. 각 문자 하나는 한 번의 움직임을 말한다. ‘F’는 앞으로 한 칸 움직인 것이고, ‘L'과 ’R'은 방향을 왼쪽 또는 오른쪽으로 전환한 것이다. 즉, 90도를 회전하면서, 위치는 그대로인 것이다.입력첫째 줄에 홍준이가 적은 내용의 길이가 주어진다. 길이는 0보다 크고..
![]()
문제풀이코너 A를 몇 번 방문해도 되는지 수식으로 구한 후, A - B가 큰 값부터 해당 개수만큼 차례대로 선택하면 된다. A - B가 음수일 때는 B를 선택함에 유념한다. 필자는 A - B에 대한 배열을 추가적으로 구현하여, 해당 배열을 정렬 후 일정 금액 초과는 반드시 선택, 일정 금액은 남은 선택 개수만큼 선택하는 방식으로 구현하였다. 코드#include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, x; cin >> n >> x; int cnt = (x - 1000 * n) / 4000; int arr[100000][2]; int diff[100000]; for (int i = 0; i cin >> ar..
![]()
문제https://www.acmicpc.net/submit/5585풀이- 거슬러 줄 돈을 계산 후 큰 동전부터 나눔chg = 1000 - int(input())coins = [500, 100, 50, 10, 5, 1]cnt = 0for c in coins: cnt = chg // coin chg %= cprint(cnt)
![]()
문제알고리즘난이도 별로 정해진 개수만큼 문제를 골라서 전체 시간을 최소화하는 문제이다.난이도를 증가시키는 경우 60분이 필요하므로 240분은 무조건 소요가 된다.시간을 최소화하려면, 해당 난이도에서 최소 시간으로 문제를 고른뒤에 해당 문제를 오름차순 정렬해서 차이가 최소화 되도록 하면 된다.먼저, 문제를 입력받고 해당 문제들을 난이도 별로 나눈다.난이도마다 오름차순으로 정렬후에 선택해야 하는 문제수만큼 작은것부터 고른다. 그렇다면 해당 난이도에서 휴식시간을 계산하기 위해 오름차순정렬해서 반복문을 할 필요없이 선택된 문제중에 최대값과 최소값의 차이로 휴식시간을 계산해 주면 된다.코드import sysinput = sys.stdin.readlinen = int(input())p = list(map(int, ..
T = int(input())for i in range(T): stack = [] a=input() for j in a: if j == '(': stack.append(j) elif j == ')': if stack: stack.pop() else: # 스택에 괄호가 없을경우 NO print("NO") break else: # break문으로 끊기지 않고 수행됬을경우 수행한다 if not stack: # break문으로 안끊기고 스택이 비어있다면 괄호가 다 맞는거다. print("YES")..
